package bfs;

//正难则反： 不知道哪个区域是否应该标记  =》 先处理不需要被标记的位置(先处理边界)
//由于会直接修改原数据，因此不需要visit数组
public class 被围绕的区域 {
	public static int l,r,m,n;
    public static int MAXM=201,MAXN=201;
    public static int[] dx={0,0,1,-1};
    public static int[] dy={1,-1,0,0};
    public static int[][] queue=new int[MAXM*MAXN][2];

    //将区域的所有的位置用'.'进行标记
    public static void bfs(char[][] grid,int i,int j){
        l=r=0;
        queue[r][0]=i;
        queue[r++][1]=j;
        while(l<r){
            int size=r-l;
            for(int t=0;t<size;t++){
                int nx=queue[l][0],ny=queue[l++][1];
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='O'){
                        queue[r][0]=x;
                        queue[r++][1]=y;
                        grid[x][y]='.';
                    }
                }
            }
        }
    }
    
    public void solve(char[][] grid) {
        m=grid.length;
        n=grid[0].length;
        for(int i=0;i<m;i++) {
        	for(int j=0;j<n;j++) {
        		//标记将所有边界区域
        		if((i==0||j==0||i==m-1||j==n-1)&&grid[i][j]=='O') {
        			grid[i][j]='.';
        			bfs(grid, i, j);
        		}
        	}
        }
        //标记完整个表只要三种： 1.X 2.一定属于内部区域的O  3.与边界连接的.
        //既然能保证剩余的O一定不会与边界连通，因此直接将其替换为X
        //同时，确定了与边界相连的O，之间还原即可，因此用for循环直接还原即可；
        for(int i=0;i<m;i++) {
        	for(int j=0;j<n;j++) {
        		if(grid[i][j]=='O') {
        			grid[i][j]='X';
        		}
        		else if(grid[i][j]=='.') {
        			grid[i][j]='O';
        		}
        	}
        }
    }
}
